import java.util.Iterator;
/**
 * Finds the max flow with Scaling Max Augmenting path version of FordFulkerson.
 * 
 * @author Geetha Sitaraman
 * 
 */

public class ScalingMaxFlow {
	    static StopWatch dfs_time ;

        public ScalingMaxFlow(){
                
        }
        
        
/**
 * Given a graph and two vertices, the method will find the max
 * flow using the scaling ford fulkerson algorithm
 * @param G  is the simple graph to find a max flow for
 * @param s  is the starting vertex
 * @param t  is the ending vertex
 * @return   integer, the max flow through 
 */
       
        public static int maxFlow(SimpleGraph G, Vertex s, Vertex t) throws Exception{
                SimpleGraph path;
                int flow,bottle_neck,scale, maxcap_C;
                Iterator i;
                Edge e, lastedge;
                Vertex v, previous;
                VertexData vdata;
                EdgeData edata;
                boolean hasPath;
                dfs_time = new StopWatch();
                double total_time_dfs = 0;
                flow = 0;
                maxcap_C = 0;
                lastedge = null;
                
                //find the maximum capacity out of S
                for (i = G.incidentEdges(s);i.hasNext(); ){
                        e = (Edge) i.next();
                        if(e.getFirstEndpoint() == s){
                        	edata = (EdgeData) e.getData();
                        	maxcap_C = maxcap_C + edata.getCapacity();
                        }
                }
                System.out.println("maximum capacity out of s is :" +maxcap_C);
                scale = highestPowerof2(maxcap_C);
                //System.out.println("Scaling factor :" +scale);
                while(scale >= 1){
                		
                        //set all vertexData visited to false for graphsearch
                        for (i = G.vertices(); i.hasNext(); ){
                                v = (Vertex) i.next();
                                vdata = (VertexData) v.getData();
                                vdata.setVisited(false);                        
                        }
                       
                        
                
                        path = GraphSearch.depthFirstSearch(G, s, t, new SimpleGraph(), scale-1);  
                        total_time_dfs = total_time_dfs + dfs_time.elapsedTime();
                                                
                        while (path.numEdges() > 0){
                        
                        	bottle_neck = maxcap_C;
                                previous = s;
                                //find the value of the bottle_neck in the path
                                for (i = path.edges(); i.hasNext(); ){
                                        e = (Edge) i.next();
                                        edata = (EdgeData) e.getData();
                                        if (e.getFirstEndpoint() == previous){
                                        	bottle_neck = min(bottle_neck, edata.getForwardCapacity());
                                                previous = e.getSecondEndpoint();
                                        } else {
                                        	bottle_neck = min(bottle_neck, edata.getBackwardCapacity());
                                                previous = e.getFirstEndpoint();
                                        }
                                        
                                }
                           
                                
                                //add or subtract the bottle_neck value to the flow of each edge in the path
                                previous = s;
                                for (i = path.edges(); i.hasNext(); ){
                                        e = (Edge) i.next();
                                        edata = (EdgeData) e.getData();
                                        if (e.getFirstEndpoint() == previous){
                                                edata.increaseFlow(bottle_neck);
                                                previous = e.getSecondEndpoint();
                                        } else {
                                                edata.decreaseFlow(bottle_neck);
                                                previous = e.getFirstEndpoint();
                                        }
                                        
                                }
                                flow += bottle_neck;
                                
                                //set all vertexData visited to false for graph search
                                for (i = G.vertices(); i.hasNext(); ){
                                        v = (Vertex) i.next();
                                        vdata = (VertexData) v.getData();
                                        vdata.setVisited(false);                        
                                }
                                path = GraphSearch.depthFirstSearch(G, s, t, new SimpleGraph(), scale-1);
                                total_time_dfs = total_time_dfs + dfs_time.elapsedTime();
                        }
                        scale = scale / 2;
                        //System.out.println("Scaling factor is now : "+ scale);
                }
                return flow;
        }
    /**
     * Finds the minimum of two given values 
     * @param x 
     * @param y
     * @return
     */

        
        private static int min(int x, int y) {
                if(x < y)
                        return x;
                return y;
        }
        
        /**
         * Finds the greatest power of 2 that is less than the number given
         * @param num - the number whose highest power of 2 needs to be computed 
         * @return  int - The highest power of 2 below num
         */
        private static int highestPowerof2(int num){
                int ans;
                ans = 1;
                
                while (ans * 2 <= num){
                        ans = ans * 2;
                }
                //System.out.println("maximum power of 2 below " + num + " is " + ans);
                return ans;
        }
}      
        
        
